#ifndef _BASELIB_SPACE_M_TRIE_
#define _BASELIB_SPACE_M_TRIE_


#include <vector>
#include <limits>
#include <algorithm>

namespace base_lib {

template<unsigned int kLettersCount, typename TChar, typename TStateId, typename TValue>
class CMorphoTrie {
public:
    typedef TStateId    TState;
    static const TState kStartState;
    static const TState kInvalidState;

    class CMorphoTrieTransition {
    public:

        typedef std::vector<TState> TTargets;

        CMorphoTrieTransition()
        : m_iModifier(0)
        , m_vNextStates(kLettersCount, kInvalidState)
        {}

        bool addTransition( TChar symbol, TState targetState )
        {
            bool    ret(false);
            TState& state(m_vNextStates[static_cast<unsigned int>(symbol)]);

            if (kInvalidState == state) {
                state   =   targetState;
                ret     =   false;
            }

            return ret;
        }

        TState transit( unsigned char symbol )const
        {
            unsigned int    sym(static_cast<unsigned int>(symbol));

            if (sym < m_iModifier) {
                return kInvalidState;
            }

            sym -=  m_iModifier;

            if (sym >= m_vNextStates.size()) {
                return kInvalidState;
            }

            return m_vNextStates[sym];
        }

        struct TValidStatePred {
            bool operator ()(TState state)
            {
                return  (kInvalidState != state);
            }
        };

        void compress()
        {
            typename TTargets::iterator  newStart(std::find_if( m_vNextStates.begin()
                                                              , m_vNextStates.end()
                                                              , TValidStatePred() ));

            m_iModifier =   std::distance( m_vNextStates.begin()
                                          , newStart );

            typename TTargets::iterator  newEnd(std::find_if( m_vNextStates.rbegin()
                                                            , m_vNextStates.rend()
                                                            , TValidStatePred() ).base());

            if (newEnd > newStart) {
                unsigned int    newLen(std::distance(newStart, newEnd));
                m_vNextStates.erase(m_vNextStates.begin(), newStart);
                newEnd  =   m_vNextStates.begin();
                std::advance(newEnd, newLen);
                m_vNextStates.erase(newEnd, m_vNextStates.end());
            }
            else {
                m_vNextStates.clear();
                m_iModifier =   kLettersCount;//every symbol is less than this
            }
        }

    private:
        unsigned int    m_iModifier;
        TTargets        m_vNextStates;
    };

    typedef std::vector<TValue>                 TValueData;
    typedef std::vector<CMorphoTrieTransition>  TTransitions;

    typedef std::vector<unsigned char>          TChain;

    CMorphoTrie()
    : m_vData(1, TValue())
    , m_vTransitions(1, CMorphoTrieTransition())
    {}

    TState  move( TState startState, TChar symbol )const
    {
        const CMorphoTrieTransition&    trans(m_vTransitions[startState]);
        return trans.transit(symbol);
    }

    TState addTransition( TState from, TChar symbol )
    {
        CMorphoTrieTransition&  trans(m_vTransitions[from]);
        TState                  to(trans.transit(symbol));
        if (kInvalidState   ==  to) {
            to  =   m_vTransitions.size();
            trans.addTransition(symbol, to);
            m_vTransitions.push_back(CMorphoTrieTransition());
            m_vData.push_back(TValue());
        }

        return to;
    }

    template<typename TIter>
    TState addChain( TIter begin, TIter end )
    {
        TState  state(kStartState);

        for (; begin != end; ++begin) {
            state   =   addTransition(state, *begin);
        }

        return state;
    }

    template<typename TIter>
    TState testChain( TIter begin, TIter end )const
    {
        TState  state(kStartState);

        while ((kInvalidState != state) and (begin != end)) {
            state   =   move(state, *begin);
            ++begin;
        }

        return state;
    }

    TValue* getValue( TState state )
    {
        if (m_vData.size() <= state) {
            return NULL;
        }

        return &m_vData[state];
    }

    const TValue* getConstValue( TState state )const
    {
        if (m_vData.size() <= state) {
            return NULL;
        }

        return &m_vData[state];
    }

    void compress()
    {
        for (unsigned int i = 0; i != m_vTransitions.size(); ++i) {
            m_vTransitions[i].compress();
        }
    }

private:
    TValueData      m_vData;
    TTransitions    m_vTransitions;
};

template<unsigned int kLettersCount, typename TChar, typename TStateId, typename TValue>
const TStateId CMorphoTrie<kLettersCount, TChar, TStateId, TValue>::kStartState   =   0;

template<unsigned int kLettersCount, typename TChar, typename TStateId, typename TValue>
const TStateId CMorphoTrie<kLettersCount, TChar, TStateId, TValue>::kInvalidState   =   std::numeric_limits<TStateId>::max();

} //namespace base_lib

#endif// _BASELIB_SPACE_M_TRIE_
